#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define Max_size 50

typedef struct //顺序串
{
    char str[Max_size];
    int length;
} SqlString;

void getNext(SqlString s, int next[])
{
    int i = 0, k = -1;
    next[0] = -1;
    while (i < s.length - 1) // next[i]的值时第i个字符前面的最长相等前后缀的的数
    {
        if (k == -1 || s.str[i] == s.str[k])
        {
            i++;
            k++;
            next[i] = k;
        }
        else
            k = next[k];
    }
}

int kmp(SqlString s, SqlString t, int i)
{
    int next[Max_size], j = 0;
    getNext(t, next);
    while (i < s.length && j < t.length)
    {
        if (j == -1 || s.str[i] == t.str[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if (j >= t.length)
        return i - t.length;
    else
        return -1;
}

int showtimes(SqlString s, SqlString t)
{
    int i = 0, count = 0;
    int index = kmp(s, t, i);
    while (index != -1)
    {
        count++;
        index = kmp(s, t, index + t.length);
    }
    return count;
}

int main()
{
    SqlString s, t;
    strcpy(s.str, "aaabbdaabbde");
    strcpy(t.str, "aabbd");
    s.length = strlen(s.str);
    t.length = strlen(t.str);
    printf("串t在串s中出现的次数为：%d", showtimes(s, t));
    return 0;
}
